1. Field of the Invention
The present invention relates to a network path controlling method and an apparatus therefor, and in particular to a method and an apparatus for controlling a hierarchized network.
As an internet/intranet is rapidly spread in offices and campuses, former experimental networks have been transforming into networks which bear the nucleus of business. Accordingly, a hierarchized network which simplifies the management of network by simplifying the composition of network has been remarkable.
2. Description of the Related Art
1. IP Address and Notation
An IPv4 (IPversion4) address which is an IP (Internet Protocol) address generally used at present has an address length of 32 bits as shown in FIG. 10, and is notated (hierarchized or layered) by the division with xe2x80x98.xe2x80x99 per an arbitrary number of e.g. 8 bits. The address is allotted to every node and is composed of two portions, i.e. a network portion indicating a network NW to which the node belongs and a host portion indicating an individual node (host) HST. Also, the bit number of an objective network portion is notated with xe2x80x98/xe2x80x99 after the IP address.
In one example of address xe2x80x9c133.160.115.5/24xe2x80x9d shown in FIG. 10, the top 24 bits (133.160.115) of xe2x80x9c133.160.115.5xe2x80x9d indicate the network portion, and xe2x80x9c5xe2x80x9d of same indicates the host portion. In addition, the IP address whose host portion is xe2x80x9c0xe2x80x9d means the network itself. Namely, the network of the address xe2x80x9c133.160.115xe2x80x9d is notated as xe2x80x9c133.160.115.0/24xe2x80x9d.
2. Composition of the Present IP Network
In the present IP networks, as shown in FIG. 11, when networks NW1 and NW2 are connected with a router RA, networks NW2 and NW3 are connected with a router RB, and networks NW2 and NW4 are connected with a router RC, the network NW1 whose address is xe2x80x9c133.160.115.0/24xe2x80x9d and the network NW3 whose address is xe2x80x9c133.160.116.0/24xe2x80x9d are not adjoining with each other, and the network NW2 lies between them.
Thus, it is possible that an arbitrary network lies between the IP networks having an address according to the above-mentioned notation, and no hierarchization based on the address is considered.
3. Path Selecting Method of IPv4.
A packet has a path (route) selection directed by an router which is set up on the boundary of the networks, and path information required for the path selection is periodically exchanged between routers.
An exchange example of the path information in the prior art is shown in FIG. 12. The path information of the address xe2x80x9c133.160.115.0/24xe2x80x9d is exchanged from the router RA into the router RB, thereby enabling the router RB to recognize the existence of the network NW1 whose address is xe2x80x9c133.160.115.0/24xe2x80x9d ahead of the address xe2x80x9c150.123.212.0/24xe2x80x9d.
Likewise, the router RA recognizes that the network NW3 whose address is xe2x80x9c133.160.116.0/24xe2x80x9d exists ahead of the network NW2 whose address is xe2x80x9c150.123.212.0/24xe2x80x9d from the path information of the router RB. The exchange of the path information between the router RC and the routers RA and RB is performed in the same way. Each of the routers tables this path information to be renewed at the next path exchange.
FIG. 13 shows an example of packet relay in the network where the path is exchanged in FIG. 12, which will be sequentially described as follows:
(1) An IP packet P1 having a destination address (Dst) xe2x80x9c133.160.116.1xe2x80x9d which has been transmitted from a host Ha to a host Hb is given to the router RA which is a router of the network NW1 whose address is xe2x80x9c133.160.115.0/24xe2x80x9d.
(2) The router RA retrieves a path information table (a routing table) about the whole network portion (133.160.116.) of the destination address at the router RA itself. In this example, the network NW3 whose address is xe2x80x9c133.160.116.0/24xe2x80x9d on the router RB and the network NW4 whose address is xe2x80x9c133.160.117.0/24xe2x80x9d on the router RC are stored in the table.
(3) As a result of the table retrieval, the router RA recognizes that the router RB is the next destination and transfers the packet P1 to the router RB.
(4) The router RB which has received the packet P1 recognizes from the network portion (133.160.116) of the packet P1 that the packet is addressed to the network NW3 which is its own subordinate, and then transfers the packet P1 to the host Hb with watching the host portion (0/24) of the packet P1.
It should be intensively noted that the path retrieval is performed about the whole of the network in the above-mentioned (2) and (4). This is because the network is not hierarchized based on the IP address so that the router RA, for instance, can not determine to which router RB or RC the packet should be transmitted only with the retrieval about a part (133.160) of the network portion.
In accordance with a recent large-scaled internet/intranet, there has been increased needs of simplifying the network composition and facilitating centralized controls. For the needs, the construction of the hierarchized IP network has been remarkable.
However, there are problems for the achievement of the above-mentioned hierarchized IP network.
{circle around (1)} A network itself has no hierarchical structure based on an IP address.
{circle around (2)} A path control has no construction attending to hierarchization.
The former problem {circle around (1)} is being solved because a new version IP=IPv6 (version6) which hierarchizes the network composition itself by promoting the address hierarchization is studied by a standardizing organization. However, the latter problem {circle around (2)} has not yet been solved.
It is accordingly an object of the present invention to provide a network path controlling method and an apparatus therefor which performs a path retrieval based on path information exchanged between routers in order that networks which share IP addresses hierarchized by arbitrarily dividing the IP addresses by an arbitrary bit length from an upper bit can be mutually connected through an upper one of hierarchized networks of the hierarchized IP addresses in which hierarchy information can be simply exchanged by limiting an area of destination address to be referred upon the path retrieval to achieve a high-speed path retrieval.
1. Basic Concept
A path control in the hierarchized network is not required to be performed to the whole of a network of IP address but has only to be performed per each hierarchy. For example, the network shown in FIG. 1 is hierarchized based on the structure of IP address.
In this example, when a host HA on a network NW111 whose address is xe2x80x9cxcex1.A.a.0/24xe2x80x9d transmits a packet P to a host HB on a network NW221 whose address is xe2x80x9cxcex2.B.a.0/24xe2x80x9d, it is enough to perform a path selection with paying attention only to xe2x80x9cxcex2xe2x80x9d at the address of the host HB in a network NW10 whose address is xe2x80x9cxcex1.0.0.0.8xe2x80x9d. However, the host HB has no need to perform the path selection until the packet enters a network NW20 whose address is xe2x80x9cxcex2.0.0.0/8xe2x80x9d. Namely, there is always no need to perform the path retrieval for the whole of network.
In this way, by the methods of {circle around (1)} exchanging not only the above-mentioned path information in the prior art but also the hierarchy information, and {circle around (2)} allotting the hierarchy information to the destination IP address of the packet, it becomes possible to perform a path selection to a part of the destination address, that is an only adequate hierarchical position in the network portion upon the path retrieval of each router.
2. Solution Means
FIG. 1 shows a hierarchized network constructed according to the rules described hereinbelow:
{circle around (1)} An upper hierarchy must include a lower hierarchy. In the example of FIG. 1, a network whose address is e.g. xe2x80x9cxcex1.B.b.0/24xe2x80x9d can not be provided between the network NW111 whose address is xe2x80x9cxcex1.A.a.0/24xe2x80x9d and a network NW112 whose address is xe2x80x9cxcex1.A.b.0/24xe2x80x9d.
{circle around (2)} The networks at the same hierarchy common to the same upper hierarchy can be connected. In the example of FIG. 1, the network NW111 whose address is xe2x80x9cxcex1.A.a.0/24xe2x80x9d and the network NW112 whose address is xe2x80x9cxcex1.A.b.0/24xe2x80x9d can be connected.
Routers R2-R6 attending to the hierarchized networks shown in FIG. 1 perform path controls for the hierarchized networks, and perform packet relay processing based on the path controls. As shown in the example of the router R4, each router has a packet transmitting/receiving means 1 shown in FIG. 2, a path table holding means 2 shown in FIG. 3, a packet preparing means 3 shown in FIG. 4, a path information receiving means 4 shown in FIG. 5, a path information transmitting means 5 shown in FIG. 6, and a relay packet processing means 6 shown in FIG. 7. Hereinafter the term xe2x80x9crouterxe2x80x9d will designate a router attending to the hierarchized network.
It is to be noted that the host HA on the hierarchized network can be composed with the packet transmitting/receiving means 1, the path table holding means 2, the packet preparing means 3, and the path information receiving means 4 among the above-noted router elements. Having functions included in the router attending to the hierarchized network which will be described below, those means 1-4 will not be hereinafter made distinguished from each other.
It is supposed that each of the means 1-6 each router holds can deal with hierarchized extensions as hierarchy information that is its own extension allotted to the IP address indicating the hierarchy of the address. These operations are performed by exchanging the hierarchized extensions of the highest hierarchized network in the hierarchized networks having the routers therebetween in the form of path information.
In this case, all of the hierarchized extensions in the received path information are held in the routers.
An address notation using the hierarchized extension is, e.g. xe2x80x9c133.160.115.0/17/24xe2x80x9d. This example indicates the hierarchy from the 17th to 24th bits of xe2x80x9c133.160.115.0xe2x80x9d, that is the hierarchy of xe2x80x9c115xe2x80x9d. In addition, the extension xe2x80x9c115/16/24xe2x80x9d indicates that the hierarchy from the 17th to 24th bits is xe2x80x9c115xe2x80x9d
Each of the means 1-6 of the router will now be described.
2.1 Packet Transmitting/Receiving Means 1 (see FIG. 2):
This is a means for transmitting/receiving the IP packet, and comprises a packet receiver 11 and a packet transmitter 12.
The packet receiver 11: This is a so-called receiving portion of the IP packet. When the packet received from the transmission line is the path information, it is transferred to the path information receiving means 4, and otherwise is transferred to the relay packet processing means 6.
The packet transmitter 12: This is a so-called transmitting portion of the IP packet. The transmission processing is performed to the packet transferred from the path information transmitting means 5 or the relay packet processing means 6 to the transmission line.
2.2 Path Table Holding Means 2 (see FIG. 3):
This is a means for holding the path information as a table, and comprises a non-hierarchized network table portion 21 and a hierarchized network table portion 22.
The non-hierarchized network table portion 21: This is a conventional table portion holding the path information to the non-hierarchized network.
The hierarchized network table portion 22: This is a table holding the path information to the hierarchized network.
2.3 Packet Preparing Means 3 (see FIG. 4):
This is a means for preparing/transmitting the packet in the own router/host serving as a transmitting source according to a demand from the upper hierarchy, and comprises a packet preparing portion 31 and a path retrieval portion 32.
The packet preparing portion 31: This is a portion for preparing the packet which the own node transmits, and has following functions;
{circle around (1)} The packet preparing portion 31 prepares the IP packet according to the instructions from the upper hierarchy;
{circle around (2)} The packet preparing portion 31 instructs the path retrieval portion 32 of the path retrieval for the packet destination address to allot the hierarchized extension based on the retrieval result if the destination is the hierarchized network;
{circle around (3)} The packet preparing portion 31 requests the packet transmitting/receiving means 1 to transmit the packet.
The path retrieval portion 32: This portion has a function of performing the path retrieval for the destination address instructed by the packet preparing portion 31 with the path table holding means 2. It is to be noted that the hierarchized extension is transferred to the packet preparing portion 31 together with the retrieval result if the retrieval result exists in the hierarchized network table portion 22.
2.4 Path Information Receiving Means 4 (see FIG. 5):
This is a means for preparing the path table based on the path information received from an adjoining router, and comprises a hierarchized network-path information extractor 41, a non-hierarchized network table constructor 42, and a hierarchized network table constructor 43.
The hierarchized network-path information extractor 41: This portion classifies entries in the path information transferred from the packet transmitting/receiving means 1 into ones of the hierarchized network or of non-hierarchized network respectively based on the presence or absence of the hierarchized extension.
The non-hierarchized network table constructor 42: This portion is a conventional path table constructor for writing entries in the path information addressed to the non-hierarchized network extracted by the hierarchized network-path information extractor 41 in the non-hierarchized network table portion 21 of the path table holding means 2.
The hierarchized network table constructor 43: This portion only extracts a hierarchy forming a retrieval object in the own router/host from the path information entries addressed to the hierarchized network extracted by the hierarchized network-path information extractor 41 to write the same in the hierarchized network table portion 22 of the path table holding means 2.
2.5 Path Information Transmitting Means 5 (see FIG. 6):
This is a means for transmitting the path information to the adjoining router or the host, and comprises a timer portion 51, a hierarchy instructor 52, and a transmitting path information preparing portion 53.
The timer portion 51: This is a conventional timer portion having a function of instructing the transmitting path information preparing portion 53 of the destination of the path information at a fixed time interval.
The hierarchy instructor 52: This has a function of notifying the transmitting path information preparing portion 53 of the hierarchy of the adjoining network to which the path information is transmitted. It is supposed that the hierarchy instructor 52 has already known the hierarchy of the adjoining network by a user""s designation or a certain means which is not described here.
The transmitting path information preparing portion 53: This portion has functions of preparing the path information by the combination of the non-hierarchized network table portion 21 and the hierarchized network table portion 22, and of transmitting the path information to the adjoining router or host via the packet transmitting/receiving means 1.
Preparing the path information by the non-hierarchized network table portion 21 is performed in the same way as the prior art. The hierarchized network table portion 22 prepares the hierarchization path information based on the instructions from the hierarchy instructor 52.
2.6 Relay Packet Processing Means 6 (see FIG. 7):
This is a means for performing the relay processing to the packet received from the packet transmitting/receiving means 1, and comprises a selector for packet addressed to hierarchization attending network 61, a packet path controller 62 addressed to the non-hierarchized network, a path table retrieval portion 63 addressed to the non-hierarchized network, a packet path controller 64 addressed to the hierarchized network, a specified hierarchy path table retrieval portion 65, an unspecified hierarchy path table retrieval portion 66, and an in-homonetwork packet transfer portion 67.
The packet selector 61: This portion has functions of determining whether or not the destination is the hierarchized network based on the existence of the hierarchized extension of the packet transferred from the packet transmitting/receiving means 1, of transferring the packet to the packet path controller 64 in case of the hierarchized network, and of transferring the packet to the packet path controller 62 in case of the non-hierarchized network.
In addition, if the bits lower than the hierarchized extension in the network portion of the destination IP address is consistent with the IP address of the network itself to which the router itself belongs, the destination host is judged to be in the network to which the router belongs, and the relaying packet is transferred to the in-homonetwork packet transfer portion 67 to deliver the packet to the destination host itself.
The packet path controller 62: This portion is a conventional path controller for instructing the path table retrieval portion 63 of the retrieval of the path table to the network portion of the packet destination address, and for transmitting the packet to the router recognized as performing a next relay processing from the retrieval result through the packet transmitting/receiving means 1.
The path table retrieval portion 63: This is a conventional path table retrieval portion for retrieving the router which is to transmit the packet next from the whole of the network portion of the packet destination address based on the non-hierarchized network table portion 21 of the path table holding means 2, and for notifying the packet path controller 62 of the retrieval result.
The packet path controller 64: This portion is a path controller for the packet addressed to the hierarchized network, which has the following functions:
{circle around (1)} When the hierarchized extension is allotted to the destination address and the destination address at the hierarchy indicated by the hierarchized extension is different from the address at the same hierarchy of the router which performs the relay processing, the controller determines that the packet has not reached the network of the hierarchy indicated by the hierarchized extension. In this case, the controller instructs the specified hierarchy packet path table retrieval portion of the path retrieval and performs the transmission processing based on the retrieval result;
{circle around (2)} In other cases, that is when the hierarchized extension is allotted to the destination address and the destination IP address at the hierarchy indicated by the hierarchized extension indicates the address at the same hierarchy of the router which is performing the relay processing, the following process is performed.
This controller determines that the packet has reached the network of the hierarchy indicated by the hierarchized extension, and instructs the unspecified hierarchy path table retrieval portion 65 to perform the path retrieval about bits lower than the hierarchized extension in the network portion of the destination IP address, and resultantly rewrites the hierarchy information notified from the unspecified hierarchy path table retrieval portion 66 to a new hierarchized extension to perform the transmission processing.
The specified hierarchy path table retrieval portion 65: This portion has functions of retrieving the path table of an area indicated by the hierarchized extension in the destination IP address with respect to the hierarchized network table portion 22 in the path table holding means 2 based on the instructions of the packet path controller 64, and of notifying the packet path controller 64 of the retrieval result.
The unspecified hierarchy path table retrieval portion 66: This portion has functions of retrieving the path table about bits lower than the hierarchized extension in the network portion of the destination IP address with respect to the hierarchized network table portion 22 of the path table holding means 2 based on the instructions of the packet path controller 64, and of notifying the packet path controller 64 of the retrieval result.
The in-homonetwork packet transfer portion 67: This is a portion of transferring the packet to the host which is in the same network as the router, which has functions of removing the hierarchized extension from the destination IP address of the packet, and of transferring the packet to the host itself which is a destination by a conventional homonetwork-transmitting means such as ARP (Address Resolution Protocol).
3. Communication Procedure
3.1 Path Information Reception
(1) The packet receiver 11 of the packet transmitting/receiving means 1 which has received a path information-exchanging packet determines that it is a packet of path information and transfers the same to the path information receiving means 4.
(2) In the hierarchized network-path information extractor 41 in the path information receiving means 4, the entries of the path information are classified depending on whether or not they are intended for the hierarchized network according to the existence of the hierarchized extension in the entries. The entries which have the hierarchized extension are transferred to the hierarchized network table constructor 43 while the entries which have no hierarchized extension are transferred to the non-hierarchized network table constructor 42.
(3) The hierarchized network table constructor 43 prepares a path table for address information of hierarchy indicated by the hierarchized extension and writes the path table in the hierarchized network table portion 22.
(4) The non-hierarchized network table constructor 42 prepares a path table which attends to no hierarchization by using the prior art and writes the path table in the non-hierarchized network table portion 21.
Thus, the path retrieval table is prepared for the path information with respect to both of the hierarchized network and the non-hierarchized network.
3.2 Path Information Transmission
(1) The timer portion 51 in the path information transmitting means 5 notifies the transmitting path information preparing portion 53 of the adjoining network to which the path information is to be transmitted.
(2) The transmitting path information preparing portion 53 prepares the path information from the non-hierarchized network table portion 21 and the hierarchized network table portion 22 as follows:
{circle around (1)} This portion prepares the entries of path information from the hierarchized network table portion 22 for hierarchies upper than the adjoining network to which the path information is to be transmitted. At this time, the hierarchized extensions are allotted to the entries in order to clarify objective hierarchies. It is to be noted that the hierarchy of the adjoining network has preliminarily been notified by the hierarchy instructor 52;
{circle around (2)} This portion prepares the entries of the path information from the non-hierarchized network table portion 21 by using the prior art.
(3) The transmitting path information preparing portion 53 prepares a path exchange packet including the entries prepared in the above mentioned item (2) and transmits the packet to the adjoining network instructed by the timer portion 51 in the above item {circle around (1)} via the packet transmitting/receiving means 1.
3.3 Packet Relay Processing
(1) The packet receiver 11 in the packet transmitting/receiving means 1 which has received a packet except the path information-exchanging packet determines that the packet is to be relayed and transfers the same to the relay packet processing means 6.
(2) The packet selector 61 of the relay packet processing means 6 determines that the destination of the packet is intended for the hierarchized network depending on whether or not the hierarchized extension is allotted to the destination IP address of the packet. The packet having the hierarchized extension is transferred to the packet path controller 64 while the packet having no hierarchized extension is transferred to the packet path controller 62. The subsequent processings are divided into three parts as follows:
(a) Relay Processing of Packet Addressed to the Non-hierarchized Network.
i. The packet path controller 62 requests the path table retrieval portion 63 to perform the path retrieval about the destination address of the packet.
ii. The path table retrieval portion 63 retrieves the router to which the packet is to be transmitted next from the non-hierarchized network table portion 21 to instruct the packet path controller 62 of the retrieval result.
iii. The packet path controller 62 transmits the packet to the router which is determined as the retrieval result via the packet transmitting/receiving means 1.
(b) Relay Processing of the Packet Addressed to the Hierarchized Network (Processing Addressed to the Same or an Upper Hierarchy)
i. The packet path controller 64 compares the destination address at the hierarchy indicated by the hierarchized extension allotted to the packet with the address at the same hierarchy of the router itself which is performing the relay processing. When these addresses are different, the hierarchized extension as well as a part of the destination address indicated by the hierarchized extension are transferred to the specified hierarchy path table retrieval portion 65.
ii. The specified hierarchy path table retrieval portion 65 retrieves the router to which the packet is to be transmitted next based on only the address of the hierarchy indicated by the hierarchized extension from the hierarchized network table portion 22 to notify the packet path controller 64 of the result.
iii. The packet path controller 64 transmits this packet to the router which is determined as the retrieval result via the packet transmitting/receiving means 1.
iv. It is to be noted that the hierarchized extension allotted to the packet is not changed in this processing.
(c) Relay Processing of the Packet Addressed to the Hierarchized Network (Processing Addressed to a Lower Hierarchy)
i. The packet path controller 64 compares the destination address indicated by the hierarchized extension allotted to the packet with the address at the same hierarchy of the router itself which is performing the relay processing.
When these addresses have the same value and bits lower than the hierarchized extension in the network portion of the destination IP address do not indicate the IP address of the network itself to which the router itself belongs, it means that the packet has reached the same hierarchy as the destination address in the hierarchy indicated by the hierarchized extension of the packet itself but that the packet has not reached the network to which the destination host belongs. For this reason, this controller instructs the unspecified hierarchy path table retrieval portion 66 to perform the path retrieval for the bits lower than the hierarchized extension in the network portion of the destination IP address.
ii. The unspecified hierarchy path table retrieval portion 66 retrieves the router which the packet is to be transmitted next based on the address transferred by the packet path controller 64 from the hierarchized network table portion 22 to notify the packet path controller 64 of the retrieval result.
It is to be noted that the hierarchized extension written in the entry of the hierarchized network table portion 22 is also notified.
iii. The packet path controller 64 rewrites the hierarchized extension allotted to the packet into the one notified from the unspecified hierarchy path table retrieval portion 66, and further transmits this packet to the router which is determined as the retrieval result via the packet transmitting/receiving means 1.
(d) Relay Processing of the Packet Addressed to the Hierarchized Network (Transfer Processing Addressed to the Host in the Same Network)
i. The packet path controller 64 compares the destination address at the hierarchy indicated by the hierarchized extension allotted to the packet with the address at the same hierarchy of the router itself which is performing the relay processing.
When the addresses have the same value and the bits lower than the hierarchized extension in the network portion of the destination IP address indicate the IP address of the network itself to which the router itself belongs, it means that the packet has reached the router of the network to which the destination host belongs. For this reason, this controller transfers the packet to the in-homonetwork packet transfer portion 67.
ii. The in-homonetwork packet transfer portion 67 removes the hierarchized extension allotted to the packet and transfers the packet to the host itself which is the destination by using a conventional in-homonetwork transmitting means such as the ARP (Address Resolution Protocol).
3.4 Packet Transmission Processing
(1) The transmission processing of the packet by the router itself as the transmitting source according to the demand from the upper hierarchy will now be described. The packet preparing portion 31 in the packet preparing means 3 prepares the IP packet based on the instructions from the upper hierarchy to instruct the path retrieval portion 32 to perform the path retrieval for the destination address instructed by the upper hierarchy.
(2) The path retrieval portion 32 performs the path retrieval for the destination address instructed by the destination packet preparing portion 31 by using the path table holding means 2. When the retrieval result reveals the entries of the hierarchized network table portion 22, the address of the router to which the packet is to be sent next as the retrieval result and the hierarchized extension the entry has are transferred to the packet preparing portion 31.
(3) When finding according to the response from the path retrieval portion 32 that the destination is the hierarchized network, the packet preparing portion 31 allots the hierarchized extension to the destination address portion of the IP packet based on the retrieval result and transmits the packet to the router which is determined as the retrieval result via the packet transmitting/receiving means 1.
(4) When the destination is the non-hierarchized network, the hierarchized extension is not allotted as usual, and the packet is transmitted to the router which is determined as the retrieval result via the packet transmitting/receiving means 1.
As mentioned above, the IP network hierarchically constructed based on the hierarchized address according to the present invention can achieve the hierarchized path control for a part of the destination address by introducing the hierarchized extension upon the path exchange time and the packet relaying time.